package 蓝桥杯算法;

import 二叉树.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class day23 {
    public static void main(String[] args) {
        day23 s=new day23();
        System.out.println(s.monotone(10));
        int[]cost={10,15,20};
        System.out.println(s.minclimb(cost));
        System.out.println(s.pathnum(2,3));
        int[][]num={{0,0,0},{0,1,0},{0,0,0}};
        System.out.println(s.pathnum2(3,3,num));
        System.out.println(s.maxleave(10));
        System.out.println(s.maxleave(2));
     int[] weight={1,3,4};
     int[] value={15,20,30};
        System.out.println(s.bag01(weight,value,4));
        System.out.println(s.bag02(weight,value,4));

    }

  public int[][] merge(int[][] nums){
      List<int[]> list=new LinkedList<>();
      Arrays.sort(nums,(x,y)->Integer.compare(x[0],y[0]));
      int start=nums[0][0];
      int end=nums[0][1];
      for(int i=1;i<nums.length;i++){
          if (nums[i][0]>=end){//说明不重叠
              list.add(new int[]{start,end});
              start=nums[i][0];
              end=nums[i][1];
          }
          else {
              end=Math.max(end,nums[i][1]);
              //没有相关添加操作，最后的结果再循环结束添加
          }
      }
      list.add(new int[] {start,end});
      return list.toArray(new int[list.size()][]);
  }
public int monotone(int n){//单调递增的数字
        String s=String.valueOf(n);
        char[] c=s.toCharArray();
        int start=s.length()-2;
        for(int i=s.length()-2;i>=0;i--){
            //从后向前遍历
            if(c[i]>=c[i+1]){
                c[i]--;
                start=i+1;//依次减小
            }
        }
        for (int i=start;i<s.length();i++){//把相关的后面的全改成9
            c[i]='9';
        }
        return Integer.parseInt(String.valueOf(c));
}
public int climb(int n){
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-1];
        }
        return dp[n];
     }
     public int minclimb(int[] cost){
        //存在顶端
        int[]dp=new int[cost.length+1];
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<=cost.length;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
     }
     public int pathnum(int m,int n){//动态规划定义好相关的dp数组
        int [][]dp=new int[m][n];
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
     }
     public int pathnum2(int m,int n,int[][]obs){
        int[][]dp=new int[m][n];
        if(obs[m-1][n-1]==1||obs[0][0]==1){
            return 0;
        }
        for(int i=0;i<m&&obs[i][0]==0;i++){
         dp[i][0]=1;
        }
        for(int i=0;i<n&&obs[0][i]==0;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = (obs[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
            }
        }
        return dp[m-1][n-1];
     }
 public int maxleave(int num){
        int[]dp=new int[num+1];
         dp[0]=0;
         dp[1]=0;
         dp[2]=1;
         for(int i=3;i<=num;i++){
             for(int j=1;j<=i-j;j++){
                 //j*dp[i-j]会增加可能的相乘次数
                 dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
             }
         }
         return dp[num];
 }
 public int maxTreenum(int num){
        int[] dp=new int[num+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=num;i++){
            for(int j=1;j<i;j++){
                dp[i]+=dp[j-1]*dp[i-1];
            }
        }
        return dp[num];
 }
 public int bag01(int[] weight,int[]value,int bagweight){
        //初始化好dp数组
      int[][]dp=new int[weight.length][bagweight+1];
      for(int i=0;i<weight.length;i++){
          for(int j=0;j<=bagweight;j++){
              dp[i][j]=0;
          }
      }
      //最开始可以放的重量
      for(int i=weight[0];i<=bagweight;i++){
          dp[0][i]=value[0];
      }
      for(int i=1;i<weight.length;i++){
          for(int j=0;j<=bagweight;j++){//一行一行遍历
              if(j<weight[i]){
                  dp[i][j]=dp[i-1][j];
              }
              else {
                  dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
              }
          }
      }
      return dp[weight.length-1][bagweight];
 }
public int bag02(int[] weight,int[] value,int bagweight) {
    int[] dp = new int[bagweight + 1];
    dp[0] = 0;
    for (int i = 0; i < weight.length; i++) {//外层循环材料
        for (int j = bagweight; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[bagweight];
}

}
